package day_2022_7_to_8.day48;

/**
 * @author haomin
 * @date 2022/08/28 17:04
 **/
public class Day43_4_Num97_IsInterleave {
    class Solution {
        public boolean isInterleave(String s1, String s2, String s3) {
            int len1 = s1.length(), len2 = s2.length(), len3 = s3.length();
            if(len1 + len2 != len3) return false;
            boolean[][] dp = new boolean[len1+1][len2+1];
            dp[0][0] = true;
            for(int i = 1; i <= len1; ++i){
                dp[i][0] = dp[i-1][0] && (s1.charAt(i-1) == s3.charAt(i-1));
            }
            for(int i = 1; i <= len2; ++i){
                dp[0][i] = dp[0][i-1] && (s2.charAt(i-1) == s3.charAt(i-1));
            }
            for(int i = 1; i <= len1; ++i){
                for(int j = 1; j <= len2; ++j){
                    dp[i][j] = dp[i-1][j] && s1.charAt(i-1) == s3.charAt(i+j-1) ||
                            dp[i][j-1] && s2.charAt(j-1) == s3.charAt(i+j-1);
                }
            }
            return dp[len1][len2];
        }
    }
}